/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja3;

/**
 *
 * @author luisorozco
 */


// Metodos copiado del libro


/**
 * Dado que el proceso de los números de clasificación consiste en mover cada valor a su 
 * ul-timate ubicación en la matriz ordenada, podemos hacer progresos hacia una solución 
 * si se podía mover un solo valor a su ubicación definitiva. Esta idea es la base de un 
 * proceso de selección rápido llamado quicksort.
 * 
 * Por esa razon en el hoja 3, se utiliza quicksort en vez de margiesort
 */

public class Sorting {
    
    
    
     public static void selectionSort (Comparable[] list){
      int min;
      Comparable temp;

      for (int index = 0; index < list.length-1; index++)
      {
         min = index;
         for (int scan = index+1; scan < list.length; scan++)
            if (list[scan].compareTo(list[min]) < 0)
               min = scan;

         // Swap the values
         temp = list[min];
         list[min] = list[index];
         list[index] = temp;
      }
   }
    
     
      private static int partition(int data[], int left, int right)
    // pre: left <= right
    // post: data[left] placed in the correct (returned) location
    {
        while (true)
        {
            // move right "pointer" toward left
            while (left < right && data[left] < data[right]) right--;
            if (left < right) swap(data,left++,right);
            else return left;
            // move left pointer toward right
            while (left < right && data[left] < data[right]) left++;
            if (left < right) swap(data,left,right--);
            else return right;
} }
      public static void quickSort(int data[], int n)
    // post: the values in data[0..n-1] are in ascending order
    {
        quickSortRecursive(data,0,n-1);
    }
      
    private static void quickSortRecursive(int data[],int left,int right)
    // pre: left <= right
    // post: data[left..right] in ascending order
    {
        int pivot;   // the final location of the leftmost value
        if (left >= right) return;
        pivot = partition(data,left,right);    /* 1 - place pivot */
        quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
        quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
        /* done! */
}

    public static void swap(int data[], int i, int j){
    // pre: 0 <= i,j < data.length
    // post: data[i] and data[j] are exchanged
        int temp;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
